#include<iostream>
#include<cstring>
#include<math.h> 
#include<algorithm>//排序、二分查找算法使用的头文件 
using namespace std;
//10:河中跳房子
long long L,N,M,rocks[50005];
bool check10(long long length){
	int now=0,num=0;
	for(int i=1;i<=N+1;i++){		
	//大于等于最短距离的石头可以跳，其他的都拆了
	//从当前的石头调到第i块石头上
		if(rocks[i]-rocks[now]>=length){
			num++;
			now=i;
		}
	}
	//移除的石头的数量要小于等于M
	if(N+1-num<=M){
		return true;
	}else{
		return false;
	}
}
/*
//03:矩形分割
int R,N,L[10005],T[10005],W[10005],H[10005];
//分割线为k时，左边的面积与右边面积的差
long long area(int k){
	long long leftArea=0,rightArea=0;
	for(int i=1;i<=N;i++){
		if(k>=L[i]&&k<=(L[i]+W[i])){
			leftArea+=(k-L[i])*H[i];
			rightArea+=(L[i]+W[i]-k)*H[i];
		}
		if(k<L[i]){
			rightArea+=W[i]*H[i];
		}
		if(k>(L[i]+W[i])){
			leftArea+=W[i]*H[i];
		}
	}
	return leftArea-rightArea;
}
int binarySplitNum(int left,int right){
	int mid=left+(right-left)/2;
	if (left+1==right) {
		if(area(right)==0||area(left)<0&&area(right)>0||area(right)<area(left)&&area(right)>0)
			return right;
		return left;
	}
	long long temp=area(mid);
	if(temp==0){
		return mid;
	}else if(temp>0){
		return binarySplitNum(left,mid);
	}else if(temp<0){
		return binarySplitNum(mid+1,right);
	}
}
*/
/*
double f(double x){
	return x*x*x*x*x-15*x*x*x*x+85*x*x*x-225*x*x+274*x-121;
}
typedef struct rectangle{
	long long L,T,W,H;
};
*/
/*
int LowerBound(int a[],int size,int p){
	int L=0;//查找区间的左端点 
	int R=size-1;//查找区间的右端点 
	int lastPos=-1;//到目前为止找到的最优解 
	while(L<=R){//如果查找区间不为空就继续查找 
		int mid=L+(R-L)/2;//取查找区间正中元素的下标 
		if(a[mid]>=p)
		R=mid-1;
		else{
			lastPos=mid;
			L=mid+1;
		}
	}
	return lastPos;
} 
*/
struct Rule1{
	bool operator()(const long long &a1,const long long &a2){
		return a1<a2;
	}
}; 
//09
/*
double L,L1;
double Binary_Search(double left,double right){
	double mid;
	double LSquare=L*L;
	
	while(right-left>0.000001){
		mid=left+(right-left)/2;
		double r2=mid+LSquare/mid/4;
		double rightV=r2*asin(L/r2);
		
		if(rightV<L1){
			left=mid;
		}else{
			right=mid;
		}
	}
	
	return mid;
}
*/
//cow
/*
long long n,c;
long long x[100005];
bool check(long long d){
	long long num=1;
	long long lastx=x[0];
	for(int i=1;i<n;i++){
		if(x[i]-lastx>=d){
			num++;
			lastx=x[i];
		}
	}
	
	if(num>=c){
		return true;
	}else{
		return false;
	}
}
*/

//04
/*
long long n,k;
long long len[10005];
bool check(long long x){
	if(x==0)
	return false;
	long long num=0;
	
	for(int i=0;i<n;i++){
		num+=len[i]/x;
	}
	
	if(num>=k)
	return true;
	else
	return false;
}
*/
int main(){
	/*
	//输入 
	int n;
	cin>>n;
	long long a[n+5];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	//二分查找需要先排序 
	sort(a,a+n);
	
	int m;
	cin>>m;
	long long target[m+5];
	for(int i=0;i<m;i++){
		cin>>target[i];
		long long *temp=lower_bound(a,a+n,target[i]);
		if(*temp==target[i]){
		//查找的值正好在输入的数据里面，输出
			cout<<target[i]<<endl;
		}else{
		//目标查找值不在数据里面，比较查找值前后的两个值与查找值哪个更接近 
			if(temp-a>0&&temp-a<n){
		//查找的位置不在起始位置，也不再结束位置 
				if((target[i]-a[temp-a-1])<=(*temp-target[i])){
					cout<<a[temp-a-1]<<endl;
				}else{
					cout<<*temp<<endl;
				}	
			}else if(temp-a==0)
		//查找的位置在起始位置
			cout<<*temp<<endl;
			else if(temp-a==n)
		//查找的位置在结束位置
			cout<<a[temp-a-1]<<endl;
			
		}
	}
	*/
	
	//02
	/*
	double low=1.5;
	double high=2.4;
	double mid=(low+high)/2;
	while(fabs(f(mid)-0)>=0.000001){
		if(f(mid)>0)
		low=mid;
		else
		high=mid;
		
		mid=(low+high)/2;
	}
	
	printf("%.6lf",mid);
	*/
	
	//没做出来 
	
	
	//03
	/*
	long long R;
	cin>>R;
	
	long long n;
	cin>>n;
	
	rectangle rec[n+5];
	for(long long i=1;i<=n;i++){
		cin>>rec[i].L>>rec[i].T>>rec[i].W>>rec[i].H;
	}
	
	long long SLift[R+5],SRight[R+5];
	long long S[R+5];
	memset(SLift,0,sizeof(SLift));
	memset(SRight,0,sizeof(SRight));
	memset(S,0,sizeof(S));
	//二分查找找出左右面积相等的那个位置 
	
	long long low=1;
	long long high=R;
	long long mid=(low+high)/2;
	for(long long i=1;i<=n;i++){
			if(mid>=(rec[i].L+rec[i].W)){
				SLift[mid]+=rec[i].W*rec[i].H;
			}else if(mid>=rec[i].L&&mid<(rec[i].L+rec[i].W)){
				SLift[mid]+=rec[i].H*(mid-rec[i].L);
				SRight[mid]+=rec[i].H*(rec[i].L+rec[i].W-mid);
			}else if(mid<rec[i].L){
				SRight[mid]+=rec[i].H*(rec[i].L+rec[i].W-mid);
			}
	}
	S[mid]=SLift[mid]-SRight[mid];
	
	while(low<=high&&S[mid]!=0){
		if(S[mid]<0){
			low=mid+1;
		}else if(S[mid]>0){
			high=mid-1;
		}
		mid=(low+high)/2;
		for(long long i=1;i<=n;i++){
			if(mid>=(rec[i].L+rec[i].W)){
				SLift[mid]+=rec[i].W*rec[i].H;
			}else if(mid>=rec[i].L&&mid<(rec[i].L+rec[i].W)){
				SLift[mid]+=rec[i].H*(mid-rec[i].L);
				SRight[mid]+=rec[i].H*(rec[i].L+rec[i].W-mid);
			}else{
				SRight[mid]+=rec[i].H*(rec[i].L+rec[i].W-mid);
			}
		}
		
		S[mid]=SLift[mid]-SRight[mid];
	}
	//该位置是左右面积相等的坐标 
	
	long long pos;
	if(mid>=1000)
	for(long long j=mid-1000;j<=mid+1000;j++){
		for(long long i=1;i<=n;i++){
			if(j>=(rec[i].L+rec[i].W)){
				SLift[j]+=rec[i].W*rec[i].H;
			}else if(j>=rec[i].L&&j<(rec[i].L+rec[i].W)){
				SLift[j]+=rec[i].H*(j-rec[i].L);
				SRight[j]+=rec[i].H*(rec[i].L+rec[i].W-j);
			}else{
				SRight[j]+=rec[i].H*(rec[i].L+rec[i].W-j);
			}
		}
		S[j]=SLift[j]-SRight[j];
		if(S[j]==0){
			pos=j;
		}
	} 
	else
	for(long long j=1;j<=R;j++){
		for(long long i=1;i<=n;i++){
			if(j>=(rec[i].L+rec[i].W)){
				SLift[j]+=rec[i].W*rec[i].H;
			}else if(j>=rec[i].L&&j<(rec[i].L+rec[i].W)){
				SLift[j]+=rec[i].H*(j-rec[i].L);
				SRight[j]+=rec[i].H*(rec[i].L+rec[i].W-j);
			}else{
				SRight[j]+=rec[i].H*(rec[i].L+rec[i].W-j);
			}
		}
		S[j]=SLift[j]-SRight[j];
		if(S[j]==0){
			pos=j;
		}
	}
	
	cout<<pos;
	*/
	
	//04
	/*
	int n,k;
	scanf("%d %d",&n,&k);
	
	int len[n+5];
	memset(len,0,sizeof(len));
	int max=-1;
	for(int i=1;i<=n;i++){
		double temp;
		scanf("%lf",&temp);
		
		len[i]=temp*100;
		if(len[i]>max)
		max=len[i];
	}
	
	
	int low=0;
	int high=max+1;
	int mid;
	while(low+1<high){
		mid=(low+high)/2;
		
		//num表示每种mid长度，一共能裁成num根网线。 
		int num=0;
		for(int i=1;i<=n;i++){
			num+=len[i]/mid;
		} 
		
		//如果能裁的网线数量多于要求，继续增加长度进行比较 
		if(num>=k){
			low=mid;
		}else if(num<k)
		//如果能裁的网线数量少于要求，减少长度进行比较
			high=mid;
	}
	
	printf("%.2lf",(low/100.00));
	
	*/
	
	
	//04
	
	/*
	cin>>n>>k;
	
	
	long long max=-1;
	for(long long i=0;i<n;i++){
		double x;
		cin>>x;
		len[i]=x*100;
		if(len[i]>max)
		max=len[i];
	}
	
	long long left=0;
	long long right=max;
	long long mid,lastmid;
	lastmid=0;
	while(left<=right){
		mid=left+(right-left)/2;
		
		if(check(mid)){
			lastmid=mid;
			left=mid+1;
		}else{
			right=mid-1;
		}
	}
	
	printf("%.2lf",lastmid/100.00);
	
	*/
	//05
	/*
	int n,f;
	cin>>n>>f;
	
	double r[n+5];
	double v[n+5];
	double max=0;
	for(int i=1;i<=n;i++){
		cin>>r[i];
		
		v[i]=r[i]*r[i]*M_PI;
		
		if(v[i]>max)
		max=v[i];
	}
	
	double low=0;
	double high=max;
	double mid;
	int num;
	while(high-low>0.000001){
		mid=(high+low)/2;
		
		//以mid为体积来分派，所能得到的块数有num个。 
		num=0;
		for(int i=1;i<=n;i++){
			num+=(int)(v[i]/mid);
		}
		
		
		//得到的块数多于f个，继续增加每个块的体积。 
		if(num>=f)
		low=mid;
		else
		//得到的块数少于等于f个，减少每个块的体积 
		high=mid;
		
	}
	printf("%.3lf",mid);
	*/
	
	
	//07
	/*
	long long n,m;
	cin>>n>>m;
	
	long long spend[n+5];
	long long totalMoney=0;
	long long max=1;
	for(long long i=1;i<=n;i++){
		cin>>spend[i];
		totalMoney+=spend[i];
		if(spend[i]>max)
		max=spend[i];
	}
	
	long long low=max;
	long long high=totalMoney;
	long long mid;
	while(low<high){
		mid=(low+high)/2;
		
		long long sum=spend[1];
		long long num=0;
		for(long long i=1;i<=n;){
			if(sum>mid){
				sum=spend[i];
				num++;
			}
			
			i++;
			sum+=spend[i];
		}
		
		
		if(num<m){
			high=mid;
		}else if(num>m){
			low=mid+1;
		}
		
	}
	
	cout<<mid;
	
	*/
	//07
	/*
	long long n;
	cin>>n;
	long long a[n+5];
	for(long long i=0;i<n;i++){
		cin>>a[i];
	}

	long long m;
	cin>>m;
	
	sort(a,a+n);
	
	for(long long i=0;i<n;i++){
		
		if(i>=n-1){
			break;
		}
		long long target=m-a[i];
		long long L=i+1;
		long long R=n-1;
		long long mid;
		while(L<=R){
			mid=L+(R-L)/2;
			
			if(a[mid]==target){
				cout<<a[i]<<' '<<target;
				return 0;
			}else if(a[mid]<target){
				L=mid+1;
			}else {
				R=mid-1;
			}
		}
		
	}
	
	cout<<"No";
	*/
	
	
	//08
	/*
	int n;
	cin>>n;
	int a[n+5];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	sort(a,a+n);
	
	cout<<a[0]<<' ';
	for(int i=1;i<n;i++){
		if(a[i]!=a[i-1])
		cout<<a[i]<<' ';
	}
	*/
	
	//09
	/*
	double C,n;
	cin>>L>>n>>C;
	
	L1=(1+n*C)*L;
	printf("%.3lf",Binary_Search(0.00,L/2));
	*/
	
	//10
	//cow
	/*
	
	cin>>n>>c;
	
	
	for(long long i=0;i<n;i++){
		cin>>x[i];
	}
	
	sort(x,x+n);
	
	long long left=0;
	long long right=1000000000/c;
	long long lastmid,mid;
	while(left<=right){
		mid=left+(right-left)/2;
		
		if(check(mid)){
			lastmid=mid;
			left=mid+1;
		}else{
			right=mid-1;
		}
	}
	
	cout<<lastmid;
	
	*/
	//03:矩形分割
	/*
	cin>>R>>N;
	for(int i=1;i<=N;i++){
		cin>>L[i]>>T[i]>>W[i]>>H[i];
	}
	int k=binarySplitNum(0,R);
	long long b=area(k);
	while(area(k)==b&&k<=R){
		k++;
	}
	if(k>=R) cout<<R;
	else cout<<k-1;
	*/
	/*
	//10:河中跳房子
	cin>>L>>N>>M;
	for(int i=1;i<=N;i++)
	cin>>rocks[i];
	rocks[N+1]=L;
	int left=0,right=L;
	int ans;
	while(left<right){
		int mid=left+(right-left)/2;
		if (check10(mid)){
			ans=mid;
			left=mid+1;
		}else{
			right=mid;
		}
	}
	cout<<ans;
	*/
	return 0;
}

